#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/8/13 11:46
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-最长回文子串.py
# @Software: PyCharm



class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        def work(ss):
            ls = len(ss)
            ml = 0
            mi = -1
            # 0
            for i in range(ls):
                ll = i+1 if i+1 < ls-i-1 else ls-i-1
                aj = 0
                for j in range(ll):
                    if ss[i-j] != ss[i+1+j]:
                        break
                    aj += 1
                if 2*aj > ml:
                    ml = 2*aj
                    mi = i+1-aj
            # 1
            for i in range(ls):
                ll = i if i < ls-i-1 else ls-i-1
                aj = 0
                for j in range(ll):
                    if ss[i-1-j] != ss[i+1+j]:
                        break
                    aj += 1
                if 2*aj+1 > ml:
                    ml = 2*aj+1
                    mi = i-aj
            return ss[mi:mi+ml]
        return work(s)


def main():
    solve = Solution()
    s = "babad"
    print(solve.longestPalindrome(s))
    s = "cbbd"
    print(solve.longestPalindrome(s))


if __name__ == '__main__':
    main()
